/*
** EPITECH PROJECT, 2018
** AlgorithmCode
** File description:二叉搜索树
** BinaryTree
*/
#ifndef BINARYTREE_H_
	#define BINARYTREE_H_

#include <functional>
#include <utility>
#include <memory>

/**
 * 二叉搜索树
 */
template<typename T, typename compare>
class SearchTree;

template<typename T, typename compare = std::less<T>>
struct TreeNode{
    T* pElem;

    TreeNode* pLeft;
    TreeNode* pRight;

    TreeNode(T* e, TreeNode* l = nullptr, TreeNode* r = nullptr):pElem(e), pLeft(l), pRight(r){

    }

    TreeNode():TreeNode(nullptr){

    }

    template<typename T1, typename compare1>
    friend class SearchTree;

private:
    void AddChildElem(T* e){
        if(pElem == nullptr)
            pElem = e;
        else{
            compare comp;
            if(comp(*e, *pElem)){ // <
                if(pLeft == nullptr){
                    pLeft = new TreeNode(e);
                    return;
                }
                pLeft->AddChildElem(e);
            }else{ // >=
                if(pRight == nullptr){
                    pRight = new TreeNode(e);
                    return;
                }
                pRight->AddChildElem(e);
            }
        }
    }

protected:
    std::pair<TreeNode*, TreeNode*> FindValue(const T& value, TreeNode* pParent){

        if(&value == pElem || *pElem == value)
            return {this, pParent};
        compare comp;
        if(pLeft && comp(*pElem,value) == 0){
            return pLeft->FindValue(value, this);
        }

        if(pRight && comp(*pElem, value) != 0){
            return pRight->FindValue(value, this);
        }

        return {nullptr, this};
    }

    /**
     * @return .first为找到的最小节点.second则为其父节点,若为nullptr, 证明pNode没有左子树
     */
    std::pair<TreeNode*, TreeNode*> GetMinimum(){
        TreeNode* pNode = this;
        TreeNode* pParent = nullptr;
        while(pNode && pNode->pLeft){
            pParent = pNode;
            pNode = pNode->pLeft;
        }

        return {pNode, pParent};
    }

    /**
     * @return .first为找到的最小节点.second则为其父节点,若为nullptr, 证明pNode没有右子树
     */
    std::pair<TreeNode*, TreeNode*> GetMaximum(){
        TreeNode* pNode = this;
        TreeNode* pParent = nullptr;
        while(pNode && pNode->pRight){
            pParent = pNode;
            pNode = pNode->pRight;
        }

        return {pNode, pParent};
    }
};

/**
 * 搜索树只负责构建树结构和引用需要添加的元素，并不会管理节点内元素的生命周期.
 * 
 */
template<typename T, typename compare = std::less<T>>
class SearchTree{
public:
    typedef  TreeNode<T, compare> NodeType;
public:
    SearchTree():root(nullptr){}
    ~SearchTree(){
        while(root){
            std::unique_ptr<NodeType> ptrTmp = Del(*root->pElem);
        }
    }

    void Add(T* elem){
        if(elem){
            if(root == nullptr)
                root = new NodeType;

            root->AddChildElem(elem);
        }
    }

    const NodeType*const GetMinimum() const{
        return root->GetMinimum().first;
    }

    const NodeType*const GetMaximum() const{
        return root->GetMaximum().first;
    }

    const NodeType*const Find(const T& value) const{
        if(root == nullptr)
            return nullptr;

        return root->FindValue(value, nullptr).first;
    }

    /** 
     * 二叉搜索树中规则就是左边的一定小于其父节点,同时关系还存在传递特性.
     * @return 返回从搜索树中移出的节点，节点的生命周期由智能指针箮理(不会管理节点内部元素的生命周期.), 
     *          nullptr没有此元素.
     * 使用者应确保不会出现内存泄漏情况，在第一时间接管节点内部的元素生命周期.
     */
    std::unique_ptr<NodeType> Del(const T& value){
        if(root){
            auto p = root->FindValue(value, nullptr);
            NodeType* pDelNode = p.first;
            if(pDelNode){
                //只有没有左子树的情况,不需要考虑有没有右子树，因为左子树是其直接后继.
                if(pDelNode->pLeft == nullptr){
                    TransPlant(pDelNode, pDelNode->pRight, p.second);
                }else //没有右子树的情况
                if(pDelNode->pRight == nullptr){
                    TransPlant(pDelNode, pDelNode->pLeft, p.second);
                }else{//左右子树都存在的情况
                    auto p1 = pDelNode->pRight->GetMinimum(); //从右子树中找，大于pDelNode->pLeft与 小于或等于pDelNode->pRight的节点
                    //返回的p1具有找到的节点还有其父节点

                    //若相等则表示pDelNode->pRight不存在左子节点
                    if(pDelNode->pRight != p1.first){
                        //若存在这样的节点则p1.first != pDelNode->pRight节点，同时p1.second也不会为nullptr
                        
                        TransPlant(p1.first, p1.first->pRight, p1.second);//这里使得相应的.second 不再指丗.first,而指向其.first->pRight
                        //在这里需要明确一点p1.first一定会是没有左子节点的(GetMinimum函数保证)
                        //使得其父节点指向其可能存在的右子树

                        p1.first->pRight = pDelNode->pRight; //将需要替换的pDelNode->pRight节点转赋上
                    }
                    
                    //更改其父节点指向，使其指向p1.first
                    TransPlant(pDelNode, p1.first, p.second);//p.second会为nullptr则pDelNode为root节点
                    
                    //更改其左子树指向
                    p1.first->pLeft = pDelNode->pLeft;
                }

                //清除其左右子树指向.
                pDelNode->pLeft = nullptr;
                pDelNode->pRight = nullptr;
            }
            return std::unique_ptr<NodeType>(pDelNode);
        }

        return std::unique_ptr<NodeType>(nullptr);
    }

private:
    NodeType* root;
    
    /**
     * 此函数的行为使用pU替换pV在其父节点中的位置.
     * 若其父节点为nullptr则其可知pV是根节点则使用成员root指针变量指向pU.
     */
    void TransPlant(NodeType* pV, NodeType* pU, NodeType* pParent){
        if(pParent == nullptr){
            root = pU;
        }else
        if(pParent->pLeft == pV){
            pParent->pLeft = pU;
        }else{
            pParent->pRight = pU;
        }
    }
};

#endif /* !BINARYTREE_H_ */
